package com.str.graphs;

import com.str.PQ.PriorityQueue;

public class Prim2 {

  private static class ElemV implements Comparable {
  	int vertex;
  	int distance;
  	
  	ElemV(int v, int d) {
  	  vertex = v;
  	  distance = d;
    }
    
    public int compareTo(Object that) {
      ElemV other = (ElemV) that;
      return distance - other.distance;
    }
  }

  private static void addEdgetoMST(int v1, int v2) {
    System.out.println("Add edge " + v1 + " to " + v2);
  }

  // Prim's MST algorithm: priority queue version
  public static void prim(Graph g, int s, PriorityQueue heap) { // v is current vertex
    boolean[] visited = new boolean[g.n()];
    int[] d = new int[g.n()];        // Distance array
    int[] p = new int[g.n()];        // Who's closest
    for (int i=0; i<g.n(); i++) {       // Initialize
      visited[i] = false;
      d[i] = Integer.MAX_VALUE;
    }
    
    d[s] = 0;    
    ElemV temp = new ElemV(s, d[s]);
    heap.add(temp);

    for (int i=0; i<g.n(); i++) {       // Now build MST    
      int v;
      do {
        if (heap.isEmpty()) return; // Nothing to remove
        temp = (ElemV) heap.removeMin();
        v = temp.vertex;
      } while (visited[v]);      
      visited[v] = true;
      if (v != s) addEdgetoMST(p[v], v); // Add edge to MST
      if (d[v] == Integer.MAX_VALUE) return; // Remaining vertices unreachable
      for (int w = g.first(v); w < g.n(); w = g.next(v,w))
        if (d[w] > g.weight(v, w)) {  // Update D
	      d[w] = g.weight(v, w);
	      p[w] = v;                   // Update who it came from
		  temp = new ElemV(w, d[w]);
	      heap.add(temp);    // Insert new distance in heap
        }
    }
  }
}